package com.itheima.leetcode.od.c.backtracking;

import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.stream.Collectors;

/**
 * <h3>考古学家</h3>
 * <h4>全排列无重复</h4>
 */
public class Archaeologist {
    static int n;
    static String[] arr;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = Integer.parseInt(sc.nextLine());
        arr = sc.nextLine().split(" ");

        getResult();
    }

    public static void getResult() {
        // 排序是为了让相同元素相邻，方便后面树层去重
        Arrays.sort(arr);

        boolean[] visited = new boolean[n];
        LinkedList<String> path = new LinkedList<>();
        HashSet<String> result = new HashSet<>();

        dfs(visited, path, result);

        // 输出石碑文字的组合（按照升序排列）
        result.stream()
                .sorted(String::compareTo)
                .forEach(System.out::println);
    }

    public static void dfs(boolean[] visited, LinkedList<String> path, HashSet<String> res) {
        if (path.size() == n) {
            res.add(path.stream().collect(Collectors.joining("")));
            return;
        }

        for (int i = 0; i < n; i++) {
            // 树层去重
            if (i > 0 && arr[i].equals(arr[i - 1]) && !visited[i - 1]) {
                continue;
            }
            if (visited[i]) {
                path.push(arr[i]);
                visited[i] = true;
                dfs(visited, path, res);
                visited[i] = false;
                path.pop();
            }
        }
    }
}